package arithmetic;

import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

/**
 * HJ43 迷宫问题
 * 知识点：
 * 1.HashMap
 * 2.向上，向下，向左，向右
 * 描述
 * 定义一个二维数组 N*M ，如 5 × 5 数组下所示：
 *
 *
 * int maze[5][5] = {
 * 0, 1, 0, 0, 0,
 * 0, 1, 1, 1, 0,
 * 0, 0, 0, 0, 0,
 * 0, 1, 1, 1, 0,
 * 0, 0, 0, 1, 0,
 * };
 *
 *
 * 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
 *
 *
 * 数据范围：
 * 2
 * ≤
 * �
 * ,
 * �
 * ≤
 * 10
 *
 * 2≤n,m≤10  ， 输入的内容只包含
 * 0
 * ≤
 * �
 * �
 * �
 * ≤
 * 1
 *
 * 0≤val≤1
 *
 * 输入描述：
 * 输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
 *
 * 输出描述：
 * 左上角到右下角的最短路径，格式如样例所示。
 *
 * 示例1
 * 输入：
 * 5 5
 * 0 1 0 0 0
 * 0 1 1 1 0
 * 0 0 0 0 0
 * 0 1 1 1 0
 * 0 0 0 1 0
 * 复制
 * 输出：
 * (0,0)
 * (1,0)
 * (2,0)
 * (2,1)
 * (2,2)
 * (2,3)
 * (2,4)
 * (3,4)
 * (4,4)
 * 复制
 * 示例2
 * 输入：
 * 5 5
 * 0 1 0 0 0
 * 0 1 0 1 0
 * 0 0 0 0 1
 * 0 1 1 1 0
 * 0 0 0 0 0
 * 复制
 * 输出：
 * (0,0)
 * (1,0)
 * (2,0)
 * (3,0)
 * (4,0)
 * (4,1)
 * (4,2)
 * (4,3)
 * (4,4)
 *
 * 复制
 * 说明：
 * 注意：不能斜着走！！
 */
public class TestHW43 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
        int num1 = in.nextInt();
        int num2 = in.nextInt();
        int[][] nums = new int[num1][num2];
        for (int i = 0; i < num1; i++) {
            for (int j = 0; j < num2; j++) {
                nums[i][j] = in.nextInt();
            }
        }
        HashMap<Integer, String> hash1 = new HashMap<>();
        hash1.put(1, "0,0");
        HashMap<Integer, String> hash2 = test2(nums, num1, num2, hash1);
        String str1 = hash2.get(1);
        String[] strs1 = str1.split(";");
        int index = 0;
        while (index < strs1.length) {
            String str2 = strs1[index];
            System.out.println("(" + str2 + ")");
            index++;
        }
    }



    public static HashMap<Integer, String> test2(int[][] nums, int num1, int num2,
                                                 HashMap<Integer, String> hashMap) {
        Set<Integer> set = hashMap.keySet();
        HashMap<Integer, String> hash2 = new HashMap<>();
        HashMap<Integer, String> hash3 = new HashMap<>();
        int index = 1;
        for (Integer i : set) {
            String str = hashMap.get(i);
            String[] strs = str.split(";");
            String[] strs2 = strs[strs.length - 1].split(",");
            int n1 = Integer.parseInt(strs2[0]);
            int n2 = Integer.parseInt(strs2[1]);
            //向下移动一位
            if (n1 + 1 < num1 && nums[n1 + 1][n2] == 0) {
                int n = n1+1;
                String ss = n + "," + n2;
                if (!str.contains(ss)) {
                    String str1 =str+ ";" + ss;
                    hash2.put(index, str1);
                    if (n == num1 - 1 && n2 == num2 - 1) {
                        hash3.put(1, str1);
                        return hash3;
                    }
                    index++;
                }
            }
            //向右移动一位
            if (n2 + 1 < num2 && nums[n1][n2 + 1] == 0) {
                int n = n2+1;
                String ss = n1 + "," + n;
                if (!str.contains(ss)) {
                    String str1 = str + ";" + ss;
                    hash2.put(index, str1);
                    if (n1 == num1 - 1 && n == num2 - 1) {
                        hash3.put(1, str1);
                        return hash3;
                    }
                    index++;
                }
            }
            //向上移动一位
            if (n1 - 1 >= 0 && nums[n1 - 1][n2] == 0) {
                int n = n1-1;
                String ss = n + "," + n2;
                if (!str.contains(ss)) {
                    String str1 = str + ";" + ss;
                    hash2.put(index, str1);
                    if (n == num1 - 1 && n2 == num2 - 1) {
                        hash3.put(1, str1);
                        return hash3;
                    }
                    index++;
                }
            }
            //向左移动一位
            if (n2 - 1 >= 0 && nums[n1][n2 - 1] == 0) {
                int n = n2-1;
                String ss = n1 + "," + n;
                if (!str.contains(ss)) {
                    String str1 = str + ";" + ss;
                    hash2.put(index, str1);
                    if (n1 == num1 - 1 && n == num2 - 1) {
                        hash3.put(1, str1);
                        return hash3;
                    }
                    index++;
                }
            }
        }
        return test2(nums, num1, num2, hash2);
    }
}
